Test 2019.10.7 题解

2019-10-07

这次试卷比较水 ~~我只考了145~~，前三道是思维题，最后一道考代码功底……

题目传送门

题解

T1

一道模拟的水题，读入后只需要把所有数的最大公因数求出来就行了，建议手打$gcd$.~~（__gcd）~~

#include<bits/stdc++.h>
using namespace std;
int n,a[501];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",a+i);
    int lg = a[1];
    for(int i=2;i<=n;i++)
        lg = __gcd(lg,a[i]);
    printf("%d\n",lg);
    return 0;
}

T2

数学题，先拆括号为a1-a2+a2-……+an-1-an，然后化简，得到最大值即为a1-an.

所以我们在读入后对数组排一遍序.

1
2
3

scanf("%d",&n);
for(re i=1;i<=n;i++)scanf("%d",&s[i]);
sort(s+1,s+n+1);

然后就很简单了.

先输出$s[n]$（最大的数）

接着从 $2$ 到 $n-1$ 输出$s[i]$

最后输出 $s[1]$

#include<bits/stdc++.h>
#define re register int
#define L 100005
using namespace std;
int n,s[L],f[L];
int main(){
    scanf("%d",&n);
    for(re i=1;i<=n;i++)scanf("%d",&s[i]);
    sort(s+1,s+n+1);
    printf("%d ",s[n]);
    for(re i=2;i<n;i++)printf("%d ",s[i]);
    printf("%d ",s[1]);
    return 0;
}

T3

一道博弈论的题目，考试的时候没想通，直接输出暴了个 $0$ 分

有不懂得地方可以参考下这篇文章: 博弈论入门

自己没怎么想懂，先贴代码，以后补坑

#include<bits/stdc++.h>
#define re register int
#define maxn 1039
using namespace std;
int t,n,s[maxn],x,y;
int main(){
//  freopen("game.in","r",stdin);
//  freopen("game.out","w",stdout);
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(re i=1;i<=n;++i)scanf("%d",&s[i]);
        for(re i=1;i<=n;++i){
            if(s[i])x++;
            else if(!s[i])break;
        }
        for(re i=n;i>0;--i){
            if(s[i])y++;
            else if(!s[i])break;
        }
        if(x%2||y%2)printf("Yes\n");
        else printf("No\n");
        x=0,y=0;memset(s,0,sizeof(s));
    }
    return 0;
}

T4

~~他死了.~~

是状态压缩动态规划 || 记忆化搜索(其实差不多)

我是打了个暴搜，正解还在打

#include<bits/stdc++.h>
#define re register int
#define L 39
#define check(); p=1;for(re j=1;j<=n;j++)if(!f[j])p=0;if(p)if(t<ans)ans=t;
using namespace std;
int n,s[L][L],f[L],p,ans=214748364;
void dfs(int x,int t){
	if(f[x]||t>ans)return;
	f[x]=1;check();f[x]=0;
	for(re y=1;y<=n;y++){
		if(y==x)continue;
		f[x]=1;dfs(y,t+s[x][y]);f[x]=0;
	}
	return;
}
int main(){
	scanf("%d",&n);
	for(re i=1;i<=n;i++)
		for(re j=1;j<=n;j++)
			scanf("%d",&s[i][j]);
	for(re i=1;i<=n;i++)dfs(i,0);
	printf("%d",ans);
	return 0;
}

PS

这好像是我留坑最多的题解了…..

-------------本文结束感谢您的阅读-------------

本文作者： jfy
本文链接： http://example.com/2019/10/07/Test%202019.10.7/
版权声明： 本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。转载请注明出处！